/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
 * 如果两个链表没有交点，返回 null 。
 */
// 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。
// 若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null
// 标记法
var getIntersectionNode = function (headA, headB) {
  while (headA) {
    headA.flag = true
    headA = headA.next
  }
  while (headB) {
    if (headB.flag) return headB
    headB = headB.next
  }
  return null
};

/**
 * 双指针法
 * 求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置
 */
var getIntersectionNode = function (headA, headB) {
  var lenA = getLen(headA);
  var lenB = getLen(headB);

  while (lenA > lenB) {
    headA = headA.next;
    lenA--;
  }

  while (lenB > lenA) {
    headB = headB.next;
    lenB--;
  }

  while (headA && headB) {
    // 就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点
    if (headA === headB)
      return headA;

    headA = headA.next;
    headB = headB.next;
  }

  return null;
};

function getLen(node) {
  var len = 0;

  while (node) {
    len++;
    node = node.next;
  }

  return len;
}

var getIntersectionNode = function (headA, headB) {
  let curA = headA, curB = headB,
    lenA = getLen(headA),
    lenB = getLen(headB);
  if (lenA < lenB) {
    // 下面交换变量注意加 “分号” ，两个数组交换变量在同一个作用域下时
    // 如果不加分号，下面两条代码等同于一条代码: [curA, curB] = [lenB, lenA]
    [curA, curB] = [curB, curA];
    [lenA, lenB] = [lenB, lenA];
  }
  let i = lenA - lenB;
  while (i-- > 0) {
    curA = curA.next;
  }
  while (curA && curA !== curB) {
    curA = curA.next;
    curB = curB.next;
  }
  return curA;
};